//给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。 
//
// 有效字符串需满足： 
//
// 
// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 每个右括号都有一个对应的相同类型的左括号。 
// 
//
// 
//
// 示例 1： 
//
// 
// 输入：s = "()" 
// 
//
// 输出：true 
//
// 示例 2： 
//
// 
// 输入：s = "()[]{}" 
// 
//
// 输出：true 
//
// 示例 3： 
//
// 
// 输入：s = "(]" 
// 
//
// 输出：false 
//
// 示例 4： 
//
// 
// 输入：s = "([])" 
// 
//
// 输出：true 
//
// 示例 5： 
//
// 
// 输入：s = "([)]" 
// 
//
// 输出：false 
//
// 
//
// 提示： 
//
// 
// 1 <= s.length <= 10⁴ 
// s 仅由括号 '()[]{}' 组成 
// 
//
// Related Topics 栈 字符串 👍 4773 👎 0


import com.itheima.datastructure.stack.Stack;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public boolean isValid(String s) {
        //这种问题根本 就想不到用栈去解决
//        Deque 是 Java 集合框架中的一个接口，全称为 Double Ended Queue（双端队列），表示一个可以在两端进行插入和删除操作的队列。
//        它继承自 Queue 接口，既可以作为普通队列（FIFO，先进先出）使用，也可以作为栈（LIFO，后进先出）使用，灵活性很高。
        // example :         Deque<String> queue = new ArrayDeque<>();
//        Java 官方更推荐使用 Deque 接口及其实现类（如 ArrayDeque）来模拟栈操作，而非直接使用 Stack 类。Stack 是 Java 早期的集合类，继承自 Vector，设计上存在一些历史遗留问题（比如所有方法都加了 synchronized 导致性能开销，且支持一些不符合栈特性的操作）
//        Deque<Character> stack = new ArrayDeque<>();
//        > 2025/08/09 01:21:35
//        解答成功:
//        执行耗时:2 ms,击败了97.70% 的Java用户
//        内存消耗:40.9 MB,击败了63.98% 的Java用户
        LinkedList<Character> stack = new LinkedList<>();
//        > 2025/08/09 01:21:05
//        解答成功:
//        执行耗时:2 ms,击败了97.70% 的Java用户
//        内存消耗:40.9 MB,击败了79.36% 的Java用户
//        ArrayDeque：基于动态数组实现，需要维护一个连续的内存空间。当栈操作涉及频繁的扩容（虽然本题中 tokens 长度有限，扩容概率低）或在数组尾部进行操作时，会有一定的内存复制开销。
//        LinkedList：基于双向链表实现，每个节点存储数据和前后指针。对于栈的 push（头部添加）和 pop（头部删除）操作，只需修改指针指向，不需要内存复制，理论上操作更轻量。
        for(int i = 0; i < s.length(); i ++){
            char c = s.charAt(i);
            if(c == '('){
                stack.push(')');
            }else if(c == '['){
                stack.push(']');
            }else if(c == '{'){
                stack.push('}');
            }else{
                if(!stack.isEmpty() && stack.peek() == c){
                    stack.pop();
                }else{
                    return false;
                }
            }
        }
        return stack.isEmpty();

    }
}
//leetcode submit region end(Prohibit modification and deletion)
